package leetcode_core.leetcode_1;

import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

public class ExamRoom {
    //将端点p映射到以p为左端点的线段
    private Map<Integer, int[]> startMap;
    //将端点p映射到以p为右端点的线段
    private Map<Integer, int[]> endMap;
    //根据线段大小长度从小到大存放所有的线段
    private TreeSet<int[]> pq;
    private int n;

    //构造函数,传入座位的总数N
    public ExamRoom(int n) {
        this.n = n;
        startMap = new HashMap<>();
        endMap = new HashMap<>();
        pq = new TreeSet<>((a,b)->{
           //算出两个线段的长度
           int distA =  distance(a);
           int distB =  distance(b);
           //长度更长的更大,排后面
            if(distA == distB){
                return b[0] - a[0];
            }
            return distA-distB;
        });
        //在有序集合中存放一个虚拟线段
        this.addInterval(new int[]{-1,this.n});
    }
    //来了一名考生,返回你给它分配的座位
    public int seat() {
        //从有序集合中拿出最长的线段
        int[] longest = pq.last();
        int x  = longest[0];
        int y  = longest[1];
        int seat;
        if(x == -1){
            //情况一:最左边没人的话肯定坐最左边
            seat = 0;
        }else if( y == this.n){
            //情况二:最右边没人,则分配右边的座位
            seat  = this.n-1;
        }else{
            //不是边界的话就坐到中间去
            seat = x + (y-x)/2;
        }
        //新建了端点后,要维护一条新的线段
        int[] left = new int[]{x,seat};
        int[] right = new int[]{seat,y};
        removeInterval(longest);
        addInterval(left);
        addInterval(right);
        return seat;
    }
    //坐在p位置的考生离开了
    public void leave(int p) {
        //将p左右的线段给找出来
        int[] right = startMap.get(p);
        int[] left = endMap.get(p);
        //将两条线段给合并为一条线段
        int[] merged = new int[]{left[0],right[1]};
        //删除旧线段,插入新线段
        removeInterval(left);
        removeInterval(right);
        addInterval(merged);
    }
    //去除线段
    private void removeInterval(int[] intv){
        pq.remove(intv);
        startMap.remove(intv[0]);
        endMap.remove(intv[1]);
    }

    //增加线段
    private void addInterval(int[] intv){
        pq.add(intv);
        startMap.put(intv[0],intv);
        endMap.put(intv[1],intv);
    }

    //计算线段的长度
    private int distance(int[] intv){
        int x = intv[0];
        int y = intv[1];
        if(x == -1){
            return y;
        }
        if(y == this.n){
            return this.n-(x+1);
        }
        //中点和端点之间的长度
        return (y-x)/2;
    }

}
